The emergence of the Internet and other large networks has increased both the number and kinds of electronic exchanges between entities. As used herein, an electronic exchange is any exchange between two or more entities over an electronic network (i.e., not in person) such as, for example, a voice communications network (e.g., POTS or PBX) or a data communications network (e.g., LAN or the Internet) or a voice-and-data communications network (e.g., voice-over-IP network). Electronic exchanges may include electronic business transactions and electronic communications. Such electronic business transactions may include the negotiation and closing of a sale of goods or services, including solicitation of customers, making an offer and accepting an offer. For example, in consumer-to-consumer electronic marketplaces (e.g., the eBay, OnSale, Yahoo and Amazon marketplaces found on the global Internet, entities may transact for the sale and purchase of goods or services.
Electronic communications also may include communications in on-line communities such as mailing lists, news groups, or web-based message boards and chat rooms, where a variety of sensitive personal information may be exchanged, including health-related data, financial investment data, help and advise on research and technology-related issues, or even information about political issues. As referred to herein, an entity may be a person or an electronic agent (e.g., a software agent). Such a person may Act as an individual (i.e., on the person's own behalf) or as a representative (e.g., officer or agent) of a corporation, partnership, agency, organization, or other group. An electronic agent may act as an agent of an individual, corporation, partnership, agency, organization, or other group.
In many electronic exchanges, an entity's identity may be anonymous to another entity. This anonymity raises several issues regarding trust and deception in connection to these exchanges. For example, an anonymous entity selling goods on-line may misrepresent the condition or worth of a good to a buyer without suffering a loss of reputation, business or other adverse effect, due to the entity's anonymity.
One solution to the problems regarding trust and deception is to provide a reputation mechanism to determine and maintain a reputation or reliability rating of an entity. Typically, a reputation mechanism is intended to provide an indication of how reliable an entity is, i.e., how truly its actions correspond to its representations, based on feedback by other entities that have conducted an electronic exchange with the entity. Such feedback typically is provided by another entity in the form of ratings in a numerical (e.g., 1-5) or Boolean (e.g., good or bad) form. In some reputation mechanisms, an average of the ratings provided by other entities are calculated to produce the reputation rating of the entity. Consequently, such reputation mechanisms typically represent the reputation of an entity with a scalar value.
Typical reputation mechanisms suffer from susceptibility to frauds or deceptions. For example, a first typical fraud occurs when an anonymous entity, after developing a poor reputation over time in an on-line community, reenters the community with a new anonymous identity (i.e., on-line name), thereby starting anew with a higher reputation than the entity's already earned poor reputation. A second typical fraud, to which typical reputation mechanisms are susceptible, occurs when two or more entities collude to provide high ratings for each other on a relatively frequent basis, such that the reputations of these entities are thereby artificially inflated.
Two reputation mechanisms that solve these two problems, Sporas and Histos, are disclosed in “Collaborative Reputation Mechanisms for On-line Communities” by Giorgos Zacharia, submitted to the Program of Media Arts and Sciences, Massachusetts Institute of Technology, Cambridge, Mass. published September, 1999 (hereinafter “the Zacharia thesis”), the contents of which are herein incorporated by reference.
Sporas is a reputation mechanism for loosely-connected communities (i.e., one in which many entities may not have had an electronic exchange with one another and thus not have rated one another.) According to the Sporas technique, a reputation may be calculated for an entity by applying the following equation:                                           R            i                    =                                    R                              i                -                1                                      +                                                            1                  C                                ·                                  damp                  ⁡                                      (                                          R                                              i                        -                        1                                                              )                                                              ⁢                                                R                  i                  other                                ⁡                                  (                                                            W                      i                                        -                                          E                      i                                                        )                                                                    ,                            Equation        ⁢                                   ⁢        1        ⁢                  :                                    where Ri-1 is the initial reputation of the entity, C is an effective number of ratings, 1/C is the change rate factor, named as such because it impacts the rate at which the reputation changes, damp (Ri-1) is a damping function, Riother is the reputation of another entity providing the rating, Wi is the rating of the entity provided by the other entity, Ei is the expected value of the rating and Ri is the reputation of the entity.        
Zacharia discloses that the damping function may be calculated by applying the following equation:                                           damp            ⁡                          (                              R                                  i                  -                  1                                            )                                =                      1            -                          1                              1                +                                  e                                                            -                                              (                                                                              R                                                          i                              -                              1                                                                                -                          D                                                )                                                              a                                                                                      ,                            Equation        ⁢                                   ⁢        2        ⁢                  :                                    where D is the size of the range of allowed reputation values and a is a so-called “acceleration” factor. The acceleration factor is named as such because its value controls a rate at which an entity's reputation changes. The Zacharia thesis further discloses that an expected rating, Ei can be calculated from the following equation:                               E          i                =                                            R                              i                -                1                                      D                    .                                    Equation        ⁢                                   ⁢        3        ⁢                  :                            
(Throughout this application, if a value represented by a symbol from a current equation was described in connection with a previously-described equation, the description of the value will not be repeated for the current equation.)
The Sporas technique implements an entity reputation mechanism based on the following principles. First, new entities start with a minimum reputation value, and build-up their reputations as a result of their activities on the system. For example, if a reputation mechanism has a rating range from 1 to 100, then an entity may start with an initial reputation value, R0, of 1. By starting with the minimum reputation value, Sporas reduces the incentive to, and effectively eliminates, that ability of an entity with a low reputation to improve the entity's reputation by reentering the system as a new anonymous identity.
Second, the reputation of an entity never falls below the reputation of a new entity. This may be ensured by applying equation 1 above. This second principle also reduces the incentive, and effectively prevents, an entity with a low reputation from reentering the system as a new anonymous entity.
Third, after each electronic exchange, the reputations of each of the two or more entities involved are updated according to the feedback or ratings provided by the other entities, where the feedback or ratings represent the demonstrated trustworthiness of the two or more entities in the latest exchange. For example, referring to Equation 1 above, the ratee reputation Ri of an entity is updated for each new rating, Wi.
Fourth, two entities may rate each other only once. If two entities exchange more than once, then, for each entity, the reputation mechanism only applies the most recently submitted rating to determine the reputation of the rated entity. This fourth principle prevents two or more entities from fraudulently inflating their reputations, as describe above, by frequently rating each other with artificially high ratings.
Fifth, entities with very high reputation values experience smaller rating changes after each update. This fifth principle is implemented by the damping function, damp(Ri-1), of Equations 1 and 2 above. The damping function, increases as the ratee reputation of the rated entity decreases, and decreases as the ratee reputation of the rated entity increases. Thus, a high reputation is less susceptible to change by a single poor rating provided by another entity.
Sixth, the reputation mechanism adapts to changes in an entity's behavior. For example, a reputation may be discounted over time so that the most recent ratings of an entity have more weight in determining the ratee reputation of the entity. For example, in Equation 1, above, ratings are discounted over time by limiting the effective number of ratings considered, C.
The Sporas reputation mechanism also weights the reputation of a rated entity according to the reputation, Rother, of another entity providing the rating, where this reputation of the other entity may be determined by applying Equation 1. Therefore, ratings from entities having relatively higher reputations have more of an impact on the reputation of the rated entity than ratings from entities having relatively lower reputations.
As described in the Zacharia thesis, Histos is a reputation mechanism better-suited for a highly-connected community, where entities have provided ratings for a significant number of the other entities. Histos determines a personalized reputation of a first entity from a perspective of a particular entity.
Histos represents the principle that a person or entity is more likely to trust the opinion of another person or entity with whom she is familiar than trust the opinion of another person or entity who she does not know. Unlike Sporas, a reputation of a first entity in Histos depends on the second entity from whose perspective the determination is made, and other ratings of the second entity provided by other users in an on-line community or population.
FIG. 1 is a block diagram illustrating a representation of an on-line community or population 300 of entities A1-A11. It interconnected by several rating links, including rating links 302, 303, 304, 306, 308 and 310. Each rating link indicates a rating of a rated entity (i.e., a ratee) by a rating entity (i.e., a rater) with an arrowhead pointing from the rating entity to the rated entity. As used herein, a ratee is an entity in a position of being rated by one or more other entities, and a rater is an entity in a position of rating one or more other entities. For example, rating link 302 represents a rating of 0.8 for ratee A3 by rater A1, and rating link 303 represents a rating of 0.9 for ratee A1 by rater A3.
Although in FIG. 1, each rating link only indicates a single rating, it is possible that an entity has provided more than one rating for another entity. The Zacharia reference discloses that if an entity has provided more than rating for another entity, the most recent rating should be selected to determine a personalized reputation of a first entity from the perspective of a second entity.
To determine a personalized reputation of a first entity from the perspective of a second entity, the first and second entity must be “connected”. A first and second entity are connected if a rating path connects the first and second entity. A rating path is a series of rating links that connect a first entity to a second entity. For example, in FIG. 1, entities A1 and A11 are connected by several rating paths, including rating paths 312 and 314. Rating path 312 includes rating links 302, 304 and 310, and rating path 314 includes rating links 302, 306 and 308.
As described in the Zacharia thesis, and referring to FIG. 1, to determine a personalized reputation of a first user from the perspective of a second user, the following methodology may be applied. First, a breadth-first search algorithm is applied to find all of the rating paths connecting A1 to A11 that are of a length less than or equal to a specified value. If a rating link indicates more than one rating, then the most recent rating is selected for the determination of the personalized reputation.
The number of rating links included in a rating path is referred to herein as the “length” of the rating path. For example, the rating path 312 has a length=3 because it includes three rating links 302, 304 and 310. Further, an entity included along a rating path between the first rated entity and the second rating entity has a “level” equal to a number of links between the entity and the second entity. For example, in FIG. 1, the entity A8 is disposed along the rating path 314. The entity A8 has a level 2 in the context of the rating path 314 because two rating links 302 and 306 lie between the entity A8 and the second entity A1. Further, an entity having a level, L, may be said to be a distance L away from the second entity.
Accordingly, the personalized reputation of a first entity from the perspective of a second entity may be determined by application of the following equation:
Accordingly, the personalized reputation of a first entity from the perspective of a second entity may be determined by application of the following equation:                                                         R              k                        ⁡                          (              n              )                                =                                    D              ·                              ∑                                  [                                                                                    R                        j                                            ⁡                                              (                                                  n                          -                          1                                                )                                                              ·                                                                  W                        jk                                            ⁡                                              (                        n                        )                                                                              ]                                                                    ∑                                                R                  j                                ⁡                                  (                                      n                    -                    1                                    )                                                                    ,                            Equation        ⁢                                   ⁢        4        ⁢                  :                                    where Rk(n) is the personalized ratee reputation of an entity k from a perspective of a second entity a distance n from the entity k, Wjk(n) is a rating provided by an entity j, located a distance n−1 from the second entity for the entity k, Rj(n−1) is the personalized ratee reputation of the entity j from the perspective of the second entity, and D is a range of allowable personalized reputation values.        
Referring to FIG. 1, the following example illustrates applying Equation 4 to determine the personalized ratee reputation of entity A11 from the perspective of entity A1, where D=1.                     R        11            =                                                  R              9                        ⁡                          (              .2              )                                +                                    R              8                        ⁡                          (              .9              )                                                            R            8                    +                      R            9                                ,                   ⁢    where                      R        9            =                                                  R              3                        ⁡                          (              .2              )                                            R            3                          =        .2              ,                   ⁢          and      ⁢                           ⁢      where                          R        8            =                                                  R              3                        ⁡                          (              .6              )                                            R            3                          =        .6              ,                   ⁢          such      ⁢                           ⁢      that                  R      11        =                                        .2            ⁢                          (              .2              )                                +                      .6            ⁢                          (              .9              )                                      .8            =              .725        .            